package greedyMind

import (
	"sort"
)

// 贪心算法解决 钱币找零问题
// 我们有 1元 ，2元，5元，10元，20元，50元，100元纸币，它们分别有c1,c2,c5,c10,c20,c50,c100张
// 现在我们要支付k元，最少要用多少张纸币

type Wallet [][2]int

func (wallet Wallet) Len() int {
	return len(wallet)
}

func (wallet Wallet) Less(i, j int) bool {
	return wallet[i][0] <= wallet[j][0]
}

func (wallet Wallet) Swap(i, j int) {
	wallet[i], wallet[j] = wallet[j], wallet[i]
}

// wallet代表钱包，k表示要支付k元
func MoneyPay(wallet Wallet, k int) (Wallet, int) {
	sort.Sort(wallet)
	var result Wallet = make([][2]int, 0)
	var wi = len(wallet) - 1 // 钱包起始支付面值
	k = moneyPay(wi, wallet, k, &result)

	return result, k
}

func moneyPay(wi int, wallet Wallet, k int, result *Wallet) int {
	for i := wi; i >= 0; i-- {
		if wallet[i][1] > 0 && k > 0 {
			if k-(wallet[i][1]*wallet[i][0]) >= 0 {
				ret := [2]int{wallet[i][0], wallet[i][1]}
				*result = append(*result, ret)
				k -= wallet[i][1] * wallet[i][0]
				wallet[i][1] = 0
			} else {
				ret := [2]int{wallet[i][0], k / wallet[i][0]}
				*result = append(*result, ret)
				wallet[i][1] -= k / wallet[i][0]
				k %= wallet[i][0]
			}
		}
	}
	return k
}
